/**
 * ****************************************************************************
 * Copyright (c) 2008 SAP AG.
 * All rights reserved. This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License v1.0
 * which accompanies this distribution, and is available at
 * http://www.eclipse.org/legal/epl-v10.html
 *
 * Contributors:
 * SAP AG - initial API and implementation
 * *****************************************************************************
 */
package org.eclipse.mat.collect;

import java.io.Serializable;
import java.util.NoSuchElementException;

public final class SetInt implements Serializable {
  private static final long serialVersionUID = 1L;

  private int capacity;
  private int step;
  private int limit;
  private int size;
  private boolean[] used;
  private int[] keys;

  public SetInt() {
    this(10);
  }

  public SetInt(int initialCapacity) {
    init(initialCapacity);
  }

  public boolean add(int key) {
    if (size == limit) {
      resize(capacity << 1);
    }
    int hash = (key & Integer.MAX_VALUE) % capacity;
    while (used[hash]) {
      if (keys[hash] == key) {
        return false;
      }
      hash = (hash + step) % capacity;
    }
    used[hash] = true;
    keys[hash] = key;
    size++;
    return true;
  }

  public boolean remove(int key) {
    int hash = (key & Integer.MAX_VALUE) % capacity;
    while (used[hash]) {
      if (keys[hash] == key) {
        used[hash] = false;
        size--;
        // Re-hash all follow-up entries anew; Do not fiddle with the
        // capacity limit (75 %) otherwise this code may loop forever
        hash = (hash + step) % capacity;
        while (used[hash]) {
          key = keys[hash];
          used[hash] = false;
          int newHash = (key & Integer.MAX_VALUE) % capacity;
          while (used[newHash]) {
            newHash = (newHash + step) % capacity;
          }
          used[newHash] = true;
          keys[newHash] = key;
          hash = (hash + step) % capacity;
        }
        return true;
      }
      hash = (hash + step) % capacity;
    }
    return false;
  }

  public boolean contains(int key) {
    int hash = (key & Integer.MAX_VALUE) % capacity;
    while (used[hash]) {
      if (keys[hash] == key) {
        return true;
      }
      hash = (hash + step) % capacity;
    }
    return false;
  }

  public int size() {
    return size;
  }

  public boolean isEmpty() {
    return size() == 0;
  }

  public void clear() {
    size = 0;
    used = new boolean[capacity];
  }

  public IteratorInt iterator() {
    return new IteratorInt() {
      int n = 0;
      int i = -1;

      public boolean hasNext() {
        return n < size;
      }

      public int next() throws NoSuchElementException {
        while (++i < used.length) {
          if (used[i]) {
            n++;
            return keys[i];
          }
        }
        throw new NoSuchElementException();
      }
    };
  }

  public int[] toArray() {
    int[] array = new int[size];
    int j = 0;
    for (int i = 0; i < used.length; i++) {
      if (used[i]) {
        array[j++] = keys[i];
      }
    }
    return array;
  }

  private void init(int initialCapacity) {
    capacity = PrimeFinder.findNextPrime(initialCapacity);
    step = Math.max(1, PrimeFinder.findPrevPrime(initialCapacity / 3));
    limit = (int) (capacity * 0.75);
    clear();
    keys = new int[capacity];
  }

  private void resize(int newCapacity) {
    int oldSize = size;
    boolean[] oldUsed = used;
    int[] oldKeys = keys;
    init(newCapacity);
    int key, hash;
    for (int i = 0; i < oldUsed.length; i++) {
      if (oldUsed[i]) {
        key = oldKeys[i];
        hash = (key & Integer.MAX_VALUE) % capacity;
        while (used[hash]) {
          hash = (hash + step) % capacity;
        }
        used[hash] = true;
        keys[hash] = key;
      }
    }
    size = oldSize;
  }
}
